package leetcode.code0810;

import java.util.Arrays;

public class Solution extends Solution810 {

	@Override
	public boolean xorGame(int[] nums) {
		Arrays.sort(nums);
		int xor = 0;// 如果只剩一个数字，按位异或运算得到它本身；起始是0
		for (int num : nums) {
			xor ^= num;
		}
		int len = nums.length;
		boolean[] flag = new boolean[len];
		return this.xorGame(nums, xor, len, flag);
	}

	public boolean xorGame(int[] nums, int xor, int size, boolean[] flag) {
		if (xor == 0)// 轮到某个玩家时，如果当前黑板上所有数字按位异或运算结果等于 0，这个玩家获胜。|| size == 0
			return true;
		if (size == 1)// 如果无数字剩余，按位异或运算结果为 0。擦完就输了
			return false;
		int last = -1;
		for (int i = 0; i < nums.length; i++) {
			if (!flag[i]) {
				int num = nums[i];
				if (last != num && (xor ^ num) != 0) {// 剩余的所有数字按位异或运算得出的结果等于 0 的话，当前玩家游戏失败。后续为0的都不能选
					flag[i] = true;
					if (!this.xorGame(nums, xor ^ num, size - 1, flag)) {
						flag[i] = false;
						return true;
					}
					flag[i] = false;
					last = num;
				}
			}
		}
		return false;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
//		so.debug1();
//		so.debug2();
		so.debug3();
	}

}
